Flip Distance Between Triangulations of a Simple Polygon is NP-Complete

摘要

Let T be a triangulation of a simple polygon. A flip in T is the operation ofremoving one diagonal of T and adding a different one such that the resultinggraph is again a triangulation. The flip distance between two triangulations isthe smallest number of flips required to transform one triangulation into theother. For the special case of convex polygons, the problem of determining theshortest flip distance between two triangulations is equivalent to determiningthe rotation distance between two binary trees, a central problem which isstill open after over 25 years of intensive study. We show that computing theflip distance between two triangulations of a simple polygon is NP-complete.This complements a recent result that shows APX-hardness of determining theflip distance between two triangulations of a planar point set.